﻿#define _CRT_SECURE_NO_WARNINGS 1
#include"LB.h"

//int removeElement(int* nums, int numsSize, int val)
// 去除数组特定元素val
//{
//    int* p = nums;
//    int k = 0;
//    for (int i = 0; i < numsSize; i++)
//    {
//        if (p[i] != val)
//        {
//            p[k] = p[i];
//            k++;
//        }
//    }
//    return k;
//}

//void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
//{
//    int p = m - 1;
//    int k = m + n - 1;
//    int g = n - 1;
//    while (p >= 0 && g >= 0)
//    {
//        if (nums1[p] >= nums2[g])
//        {
//            nums1[k--] = nums1[p--];
//        }
//        else
//        {
//            nums1[k--] = nums2[g--];
//        }
//    }
//    while (g >= 0)
//    {
//        nums1[k--] = nums2[g--];
//    }
//}

//打印
void print(LB* pa)
{
	assert(pa);
	LB* ka = pa;
	while (ka)
	{
		printf("%d->", ka->data);
		ka = ka->next;
	}
	printf("NULL\n");
}

//申请空间
LB* SQn(SPY x)
{
	LB* newn = (LB*)malloc(sizeof(LB));
	if (newn == NULL)
	{
		perror("mallloc fail!");
		exit(-1);
	}
	//申请成功
	newn->data = x;
	newn->next = NULL;
	return newn;
}

//尾插
void LBpushback(LB** ppa, SPY x)
{
	assert(ppa);
	LB* newn = SQn(x);
	if (*ppa == NULL)
	{
		*ppa = newn;
	}
	else
	{
		//找尾
		//LB* newn = SQn(x);
		LB* pp1 = *ppa;
		while (pp1->next)
		{
			pp1 = pp1->next;
		}//此时p1是尾节点
		pp1->next = newn;
	}
}

//头插
void LBpushfrond(LB** ppa, SPY x)
{
	LB* newn = SQn(x);
	newn->next = *ppa;
	*ppa = newn;//???????????
}

//尾删
void LBTopBack(LB** ppa)
{
	assert(ppa);
	assert(*ppa);//链表不能为空

	if ((*ppa)->next == NULL)//链表只有一个节点
	{
		free(*ppa);
		*ppa = NULL;
	}
	else
	{
		//链表有多个节点
		LB* pr = *ppa;
		LB* pl = *ppa;
		while (pl->next)
		{
			pr = pl;
			pl = pl->next;
		}
		free(pl);
		pl = NULL;
		pr->next = NULL;
	}
}

//头删
void LBTopFront(LB** pa)
{
	assert(pa);
	assert(*pa);
	LB* p1 = (*pa)->next;
	free(*pa);
	*pa = p1;
}

//查找
LB* LBFind(LB* pa, SPY x)
{
	LB* p1 = pa;
	while (p1)
	{
		if (p1->data == x)
		{
			return p1;
		}
		p1 = p1->next;
	}
	return NULL;
}

//在                    指定位置  之前插⼊数据
void LBInsert(LB** ppa, LB* pos, SPY x)
{
	assert(ppa);
	assert(*ppa);
	assert(pos);
	LB* p1 = *ppa;
	LB* newn = SQn(x);
	if (pos == *ppa)
	{
		LBpushfrond(ppa, x);
	}
	else
	{
		while (p1)
		{
			if (p1->next == pos)
			{
				p1->next = newn;
				newn->data = x;
				newn->next = pos;
				break;
			}
			p1 = p1->next;
		}
	}
}

//指定位置之后插⼊数据
void LBInsertAr(LB* pos, SPY x)
{
	assert(pos);
	LB* newn = SQn(x);
	newn->next = pos->next;
	pos->next = newn;
}

//删除pos节点
void LBErase(LB** ppa, LB* pos)
{
	assert(ppa);
	assert(*ppa);
	assert(pos);
	LB* pr = *ppa;
	if (pos == pr)//pos是头结点的情况
	{
		LBTopFront(ppa);//直接调用头删
	}
	else
	{
		while (pr->next != pos)
		{
			pr = pr->next;
		}
		pr->next = pos->next;
		free(pos);
		pos = NULL;
	}
}

//删除pos之后的节点
void LBEraseA(LB* pos)
{
	assert(pos);
	assert(pos->next);
	LB* pq = pos->next;
	pos->next = pos->next->next;
	free(pq);
	pq = NULL;
}

//销毁链表
void LBXH(LB** ppa)
{
	LB* p1 = *ppa;
	while (p1)
	{
		LB* p2 = p1->next;
		free(p1);
		p1 = p2;
	}
	*ppa == NULL;
}